package com.example;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @Author loubobooo
 * @Description #23. 合并K个升序链表
 * @Date 2022/2/21
 */
public class MergeJSortedLists {

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 方法描述:给你一个链表数组，每个链表都已经按升序排列。
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     * 示例 1：
     *
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     *   1->4->5,
     *   1->3->4,
     *   2->6
     * ]
     * 将它们合并到一个有序链表中得到。
     * 1->1->2->3->4->4->5->6
     * @param: [lists]
     * @return: com.example.MergeJSortedLists.ListNode
     * @author: loubobooo
     * @date: 2022/2/21
     */
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> list = new ArrayList<>();
        for (ListNode l : lists) {
            while (l != null) {
                list.add(l.val);
                l = l.next;
            }
        }
        ListNode result = new ListNode(0);
        ListNode listNode = result;
        if (list != null && list.size() > 0) {
            list.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            });
            for (int i = 0; i < list.size(); i++) {
                listNode.next = new ListNode(list.get(i));
                listNode = listNode.next;
            }
        }
        return result.next;
    }
}
